package com.xiaoyu.linkedArray;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * @program: DS_and_A
 * @description:
 * 给定一个链表，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 *
 * @author: YuWenYi
 * @create: 2021-04-27 10:38
 **/
public class HasCycle {
    public static boolean hasCycle(ListNode head) {
        /*        //自己所写的方案,使用了pos用来提示,但其实对这道题并无太大帮助
        int pos = -1;   //用来记录成环的位置
        int k = 0;      //用来记录当前链表的位置
        ArrayList<ListNode> nodeAddresses = new ArrayList<>(); //用来记录所有链表结点的地址的集合
        while (head!=null){ //链表迭代
            if (!nodeAddresses.contains(head)){  //如果地址中不包含当前的结点,那么就把当前结点的地址加到集合中
                nodeAddresses.add(head);
            }else {   //如果包含当前的结点,说明出现了环,则改变pos,然后结束循环
                pos = k;
                break;
            }
            head = head.next;
            k++;
        }
        System.out.println(pos);
        return pos!=-1;*/

        //优化解法,不考虑pos
        HashSet<ListNode> nodes = new HashSet<>();
        while (head!=null){
            //如果有元素无法添加到set中,那么就说明这个元素已经出现过了,那么就代表着出现了环
            if (!nodes.add(head)){
                return true;
            }
            head = head.next;
        }
        //如果到了这里,就代表没出现环
        return false;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4))));
        l1.next.next.next.next = l1.next.next;
        boolean hasCycle = hasCycle(l1);
        System.out.println("是否有环--->"+hasCycle);
    }
}
